package com.shakespace.algorithm.binary_tree

import com.shakespace.algorithm.common.createTreeFromLevelOrder

/**
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 */

fun main() {
    val root = arrayOf(1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9)
    val rootNode = createTreeFromLevelOrder(root)
    preorderTraversal(rootNode)
}

fun preorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    preorder(root, result)
    return result
}

/**
 * 二叉树的遍历主要看 中间值什么实收遍历
 * 前序遍历 中左右 即先遍历中
 * 中序遍历 左中右  中间值在中间
 * 后序遍历 左右中 中间值在最后
 */
private fun preorder(node: TreeNode?, result: MutableList<Int>) {
    if (node == null) return
    result.add(node.value)
//    println(result)
    preorder(node.left, result)
//    println(result)
    preorder(node.right, result)
//    println(result)
}

//fun preorderTraversal(root: TreeNode?): List<Int> {
//    if (root == null) return emptyList()
//    val list = mutableListOf<Int>()
//    list.add(root.value)
//    list.addAll(preorderTraversal(root.left))
//    list.addAll(preorderTraversal(root.right))
//    return list
//}